# class ElemType:
#     def __init__(self, key, otherinfo=""):
#         self.key = key  # 关键字域
#         self.otherinfo = otherinfo  # 其他域
#
#
# class SSTable:
#     def __init__(self):
#         self.r = [ElemType(0)]  # 存储空间基地址，r[0]闲置不用
#         self.length = 0  # 当前长度
#
#     def create_st(self, n):
#         # 创建顺序表
#         self.length = n  # 定义顺序表的长度为n
#         for i in range(n):  # 依次插入关键字
#             self.r.append(ElemType(int(input())))
#
#     def search_bin(self, key):
#         # 算法7.3折半查找
#         low = 1
#         high = self.length  # 置查找区间初值
#         while low <= high:
#             mid = (low + high) // 2  # 计算中间位置，补全此处
#             if key == self.r[mid].key:
#                 return mid  # 找到待查元素
#             elif key < self.r[mid].key:
#                 high = mid - 1  # 继续在前一子表进行查找，补全此处
#             else:
#                 low = mid + 1  # 继续在后一子表进行查找，补全此处
#         return 0  # 表中不存在待查元素
#
#
# if __name__ == '__main__':
#     st = SSTable()  # 初始化顺序表
#     n = int(input("请输入顺序表的长度："))
#     print("请输入所有关键字，每输入一个关键字按回车换行：")
#     st.create_st(n)  # 创建顺序表
#     key = int(input("请输入要查找的关键字："))
#     locate = st.search_bin(key)  # 利用折半查找在顺序表中查找该关键字的位置
#     if locate == 0:
#         print("未找到该关键字！")
#     else:
#         print("该关键字位于第{}个位置。".format(locate))


M = 16  # 散列表的表长
NULLKEY = -1  # 单元为空的标记


class HashNode:
    def __init__(self, key=NULLKEY, otherinfo=""):
        self.key = key  # 关键字项
        self.otherinfo = otherinfo  # 其他数据项


class HashTable:
    def __init__(self):
        self.ht = []  # 散列表
        for i in range(M):
            self.ht.append(HashNode())

    def h(self, key):
        # 散列函数
        return key % 13

    def insert_hash(self, key):
        # 向散列表中插入关键字
        h0 = self.h(key)
        for i in range(M):
            hi = (h0 + i) % M
            if self.ht[hi].key == NULLKEY:  # 若单元h0为空，直接插入
                self.ht[hi].key = key
                return

    def create_hash(self, n):
        # 创建散列表
        for i in range(n):
            key = int(input())
            self.insert_hash(key)

    def search_hash(self, key):
        # 在散列表ht中查找关键字为key的元素，若查找成功，返回散列表的单元标号，否则返回 - 1
        h0 = self.h(key)  # 根据散列函数h（key）计算散列地址
        if self.ht[h0].key == NULLKEY:
            return -1  # 若单元h0为空，则所查元素不存在
        elif self.ht[h0].key == key:
            return h0  # 若单元h0中元素的关键字为key，则查找成功
        else:
            for i in range(1, M):
                hi = (h0 + i) % M  # 按照线性探测法计算下一个散列地址hi
                if self.ht[hi].key == NULLKEY:
                    return -1  # 若单元hi为空，则所查元素不存在
                elif self.ht[hi].key == key:
                    return hi  # 若单元hi中元素的关键字为key，则查找成功
        return -1

    def show_table(self):
        # 显示哈希表
        for i in range(M):
            print(i, end='\t')
        print()
        for i in range(M):
            if self.ht[i].key!= NULLKEY:
                print(self.ht[i].key, end='\t')
            else:
                print("*", end='\t')
        print()


if __name__ == '__main__':
    ht = HashTable()  # 初始化散列表
    n = int(input("请输入关键字个数："))
    print("请输入所有关键字，每输入一个关键字按回车换行：")
    ht.create_hash(n)  # 创建散列表
    print("哈希表为：")
    ht.show_table()
    key = int(input("请输入要查找的关键字："))
    locate = ht.search_hash(key)  # 在散列表中查询该关键字
    if locate == -1:
        print("未找到该关键字！")
    else:
        print("该关键字位于第%d个位置。" % (locate + 1))